// https://leetcode.cn/problems/insert-into-a-binary-search-tree/
public class InsertVal {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }
    class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            if(root == null)  return new TreeNode(val);
            TreeNode point = root;
            TreeNode pre = root;
            while(point != null)
            {

                pre = point;
                if(point.val < val)
                {
                    point = point.right;
                }else
                {
                    point = point.left;
                }
            }

            if(val > pre.val){
                pre.right = new TreeNode(val);
            }
            // System.out.print(pre.val);
            if(val < pre.val){
                pre.left = new TreeNode(val);
            }

            return root;

        }


    }
}
